package chapter01_stackandqueue;

import java.util.Stack;

/**
 * 描述：
 *      仅用递归逆序栈
 * @author hl
 * @date 2021/1/14 10:31
 */
public class ReverseStack {

    public static void reverse(Stack<Integer> stack){
        if (stack.isEmpty()) {
            return ;
        }
        Integer i = getAndRemoveLast(stack);
        reverse(stack);
        stack.push(i);
    }

    /**
     * 删除栈底元素并返回
     * @param stack
     * @return
     */
    private static int getAndRemoveLast(Stack<Integer> stack) {
        Integer pop = stack.pop();
        if (stack.isEmpty()) {
            //最后一个元素直接返回，不重新压入
            return pop;
        }
        int last = getAndRemoveLast(stack);
        //重新压入
        stack.push(pop);
        return last;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
        }
        System.out.println(stack);
        reverse(stack);
        System.out.println(stack);
    }

}
